//
//  Copyright (C) 2012  Lynx Fang<lynx.cpp@gmail.com>
//
//  This program is a part of large-int.
//
//  Large-int is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  Large-int is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class large_int;

class basic_large_int
{
    friend class large_int;
    friend basic_large_int operator+(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator-(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator*(const basic_large_int &,const basic_large_int &);
    friend basic_large_int operator/(basic_large_int ,const basic_large_int &);
    friend basic_large_int operator%(basic_large_int ,const basic_large_int &);
    friend bool operator==(const basic_large_int &,const basic_large_int &);
    friend bool operator!=(const basic_large_int &,const basic_large_int &);
    friend bool operator<(const basic_large_int &,const basic_large_int &);
    friend bool operator>(const basic_large_int &,const basic_large_int &);
    friend bool operator<=(const basic_large_int &,const basic_large_int &);
    friend bool operator>=(const basic_large_int &,const basic_large_int &);
    vector<int> a;

    public:
    basic_large_int();
    basic_large_int(const int &x);
    basic_large_int(const large_int &x);

    basic_large_int(string s);
    int len() const;
    void minimize_length();
    string str() const;
    int operator[](const int &x) const;
    basic_large_int operator=(const int &x);
    basic_large_int operator+=(const basic_large_int &y);
    basic_large_int operator-=(const basic_large_int &y);
    basic_large_int operator/=(const basic_large_int &y);
    basic_large_int operator*=(const basic_large_int &y);
    basic_large_int operator%=(const basic_large_int &y);

    private:
    void carry();
};

istream& operator>>(istream &is,basic_large_int &x);
ostream& operator<<(ostream &os,const basic_large_int &x);
basic_large_int operator+(const basic_large_int &,const basic_large_int &);
basic_large_int operator-(const basic_large_int &,const basic_large_int &);
basic_large_int operator*(const basic_large_int &,const basic_large_int &);
basic_large_int operator/(basic_large_int ,const basic_large_int &);
basic_large_int operator%(basic_large_int ,const basic_large_int &);
bool operator==(const basic_large_int &,const basic_large_int &);
bool operator!=(const basic_large_int &,const basic_large_int &);
bool operator<(const basic_large_int &,const basic_large_int &);
bool operator>(const basic_large_int &,const basic_large_int &);
bool operator<=(const basic_large_int &,const basic_large_int &);
bool operator>=(const basic_large_int &,const basic_large_int &);


inline basic_large_int::basic_large_int() { a.resize(1); a[0] = 0; }
inline basic_large_int::basic_large_int(const int &x)
{
    a.resize(1);
    a[0] = x;
    carry();
}

inline void basic_large_int::minimize_length() { a.resize(len()); }
inline int basic_large_int::operator[](const int &x) const { return a[x]; }

inline int basic_large_int::len() const
{
    int ret = a.size() - 1;
    while (ret>0){
        if (a[ret]!=0)
            break;
        ret --;
    }
    return ret + 1;
}


inline bool operator!=(const basic_large_int &x,const basic_large_int &y) { return !(x==y); }

inline bool operator<=(const basic_large_int &x,const basic_large_int &y) { return !(x>y); }
inline bool operator>=(const basic_large_int &x,const basic_large_int &y) { return !(x<y); }

inline basic_large_int operator+(const basic_large_int &x,const basic_large_int &y)
{
    basic_large_int ans;
    ans = x;
    ans += y;
    return ans;
}

inline basic_large_int operator-(const basic_large_int &x,const basic_large_int &y)
{
    basic_large_int ans;
    ans = x;
    ans -= y;
    return ans;
}

inline basic_large_int basic_large_int::operator*=(const basic_large_int &y) { return (*this) = (*this)*y; }
inline basic_large_int basic_large_int::operator/=(const basic_large_int &y) { return (*this) = (*this)/y; }
inline basic_large_int basic_large_int::operator%=(const basic_large_int &y) { return (*this) = (*this)%y; }


class large_int
{
    friend class basic_large_int;
    friend large_int operator+(const large_int &x,const large_int &y);
    friend large_int operator-(const large_int &x,const large_int &y);
    friend large_int operator*(const large_int &x,const large_int &y);
    friend large_int operator/(const large_int &x,const large_int &y);
    friend large_int operator%(const large_int &,const large_int &);
    friend bool operator==(const large_int &x,const large_int &y);
    friend bool operator>=(const large_int &x,const large_int &y);
    friend bool operator<=(const large_int &x,const large_int &y);
    friend bool operator>(const large_int &x,const large_int &y);
    friend bool operator<(const large_int &x,const large_int &y);
    basic_large_int p;
    bool positive;

    public:
    large_int();
    large_int(const int &x);
    large_int(const basic_large_int &p0,const bool &pos0);
    large_int(const basic_large_int &p0);

    large_int(string s);
    string str() const;
    int operator[](const int x) const;
    int len() const;
    large_int& operator+=(const large_int &y);
    large_int& operator-=(const large_int &y);
    large_int& operator*=(const large_int &y);
    large_int& operator/=(const large_int &y);
    large_int& operator%=(const large_int &y);
    large_int& operator-();
};

ostream& operator<<(ostream &,const large_int &);
istream& operator>>(istream &,const large_int &);
large_int operator+(const large_int &,const large_int &);
large_int operator-(const large_int &,const large_int &);
large_int operator*(const large_int &,const large_int &);
large_int operator/(const large_int &,const large_int &);
large_int operator%(const large_int &,const large_int &);
bool operator==(const large_int &,const large_int &);
bool operator!=(const large_int &,const large_int &);
bool operator<(const large_int &,const large_int &);
bool operator>(const large_int &,const large_int &);
bool operator<=(const large_int &,const large_int &);
bool operator>=(const large_int &,const large_int &);

inline basic_large_int::basic_large_int(const large_int &x) { (*this)=x.p; }

inline large_int::large_int():p(0),positive(1) { }
inline large_int::large_int(const int &x):p(abs(x)),positive(x>=0) { }
inline large_int::large_int(const basic_large_int &p0,const bool &pos0):p(p0),positive(pos0) { }
inline large_int::large_int(const basic_large_int &p0):p(p0),positive(1) { }

inline int large_int::operator[](const int x) const { return p.a[x]; }
inline int large_int::len() const { return p.len(); }

inline large_int::large_int(string s)
{
    positive = 1;
    if (s=="")
        return ;
    positive = 1;
    if (s[0]=='-'){
        p = basic_large_int(s.substr(1,s.size() - 1));
        positive = 0;
    }
    else if (s[0]=='+')
        p = basic_large_int(s.substr(1,s.size() - 1));
    else
        p = basic_large_int(s);
}

inline string large_int::str() const
{
    string ret = "";
    if (!positive && !(this->p == 0))
        ret = "-";
    ret += p.str();
    return ret;
}

inline ostream& operator<<(ostream& os,const large_int &x)
{
    os << x.str();
    return os;
}

inline istream& operator>>(istream& is,large_int &x)
{
    string tmp;
    is >> tmp;
    x = large_int(tmp);
    return is;
}

inline large_int operator+(const large_int &x,const large_int &y)
{
    if (x.positive==y.positive)
        return large_int((x.p) + (y.p),x.positive);
    if ((x.p)>(y.p))
        return large_int((x.p) - (y.p),x.positive);
    else
        return large_int((y.p) - (x.p),y.positive);
}

inline large_int operator-(const large_int &x,const large_int &y) { return x + large_int((y.p),!y.positive); }
inline large_int operator*(const large_int &x,const large_int &y) { return large_int((x.p)*(y.p),!(x.positive ^ y.positive)); }
inline large_int operator/(const large_int &x,const large_int &y) { return large_int((x.p)/(y.p),!(x.positive ^ y.positive)); }
inline large_int operator%(const large_int &x,const large_int &y) { return large_int(x.p%y.p,!(x.positive ^ y.positive)); }

inline large_int& large_int::operator+=(const large_int &y) { return (*this)=(*this)+y; }
inline large_int& large_int::operator-=(const large_int &y) { return (*this)=(*this)-y; }
inline large_int& large_int::operator*=(const large_int &y) { return (*this)=(*this)*y; }
inline large_int& large_int::operator/=(const large_int &y) { return (*this)=(*this)/y; }
inline large_int& large_int::operator%=(const large_int &y) { return (*this)=(*this)%y; }
inline large_int& large_int::operator-() { this->positive = this->positive ^ 1; return (*this); }

inline bool operator==(const large_int &x,const large_int &y) { return (x.positive==y.positive || (x==0)) && (x.p==y.p); }
inline bool operator!=(const large_int &x,const large_int &y) { return !(x==y); }

inline bool operator>(const large_int &x,const large_int &y)
{
    if (x.positive!=y.positive) return x.positive>y.positive;
    if (x.positive)
        return x.p>y.p;
    else
        return x.p<y.p;
}

inline bool operator<(const large_int &x,const large_int &y)
{
    if (x.positive!=y.positive) return x.positive<y.positive;
    if (x.positive)
        return x.p<y.p;
    else
        return x.p>y.p;
}

inline bool operator>=(const large_int &x,const large_int &y) { return !(x<y); }
inline bool operator<=(const large_int &x,const large_int &y) { return !(x>y); }
